package 练习;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 希尔排序
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/4/27 0:03
 */
public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr = {15, 9, 7, 8, 20, -1, 4};
        shellSort(arr);

    }

    public static void shellSort(int[] arr) {
        int length = arr.length;
        int n = length / 2;
        int[] gap = new int[n];
        int index = n - 1;
        while (n != 0) {
            gap[index--] = n;
            n /= 2;
        }
        int gapIndex = gap.length - 1;
        while (gapIndex >= 0) {
            int val = gap[gapIndex];
            for (int i = val; i < length; i++) {
                for (int j = i; j - val >= 0 && arr[j] < arr[j - val]; j -= val) {
                    int temp = arr[j - val];
                    arr[j - val] = arr[j];
                    arr[j] = temp;
                }
            }
            for (int i : arr) {
                System.out.print(i+"\t");
            }
            System.out.println();
            gapIndex--;
        }
    }
}
